package implementations;

import java.util.Random;

public class QuickRandomized {

	// cria o objeto do gerador randomico
	private static Random random = new Random();
	
	
    public static int[] quickSort(int[] array){
        quick(array,0,array.length - 1);
        return array;
    }
    
	
    public static void quick(int[] array,int bot, int top){
        if(bot >= top){
            return;
        }

        int partition = partition(array,bot,top);

        quick(array,bot,partition-1);
        quick(array,partition + 1, top);
    }
	
	private static int partition(int[] array, int bot, int top) {
        int number = random.nextInt((top-bot)+1) + bot;
        int pivot = array[number];
        swap(array,bot,number);

        int i = bot + 1;
        int j = top;
        while(i <= j){
            if(array[i] <= pivot){
                i++;
            }else if (array[j] >= pivot){
                j--;
            }else{
                swap(array,i,j);
            }
        }

        swap(array,j,bot);
        return j;
    }
	
	// realiza a troca dos elementos
	private static void swap(int[]array, int a, int b) {
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}

}
